User blog:B1mb0w/General Proof of Strong D Function Growth Rate
This is the general proof of the Strong D Function growth rate. It will focus on 3 parameter functions of the form D(l,m,n) and the proof will be extended later for larger numbers of parameters. Strong D Functions D(m,n) with 2 Parameters For 2 parameters the Strong D Function is the same as the Deeply Nested Ackermann Function which uses the small d notation. Refer to the Comparison Rule C1 on that blog for the proof of the following: \(d(m,n) >> f_{m-1}(n+2)\) then \(D(4,1) >> f_{3}(3) = f_{\omega}(3)\) \(D(n+1,n+1) >> f_n(n+3) >> f_n(n) = f_{\omega}(n)\) This is the growth rate of the 2 parameter function Strong D Functions D(l,m,n) with 3 Parameters \(D(1,0,0) = D(0,D(0,1,1),D(0,1,1)) = D(D(1,1),D(1,1)) = D(4,4) >> f_{\omega}(3)\) \(D(1,0,1) = D(0,D(1,0,0),D(1,0,0)) = D(D(4,4),D(4,4)) >> D(f_{\omega}(3),f_{\omega}(3))\) \(>> f_{f_{\omega}(3)}(f_{\omega}(3)) = f_{\omega}(f_{\omega}(3)) >> f_{\omega}(a)\) for any \(a < f_{\omega}(3)\) \(D(1,0,2) = D(0,D(1,0,1),D(1,0,1)) >> D(f_{\omega}(a),f_{\omega}(a)) >> f_{f_{\omega}(a)}(f_{\omega}(a))\) \(= f_{\omega}(f_{\omega}(a)) >> f_{\omega}(b)\) for any \(b < f_{\omega}(a)\) First calculation - getting to \(\omega\) \(D(1,0,n) >> f_{\omega}(n+\delta)\) where \(\delta >> n\) and \(D(1,0,n) >> f_{\omega}(n.2)\) Next calculation - getting to \(\omega+1\) \(D(1,0,n+1) = D(0,D(1,0,n),D(1,0,n)) >> f_{f_{\omega}(n.2)}(f_{\omega}(n.2)) = f_{\omega}(f_{\omega}(n.2)) = f_{\omega}^2(n.2)\) \(D(1,0,n+2) = D(0,D(1,0,n+1),D(1,0,n+1)) >> f_{f_{\omega}^2(n.2)}(f_{\omega}^2(n.2)) = f_{\omega}(f_{\omega}^2(n.2)) = f_{\omega}^3(n.2)\) \(D(1,0,n+n) >> f_{f_{\omega}^{n-1}(n.2)}(f_{\omega}^{n-1}(n.2)) = f_{\omega}(f_{\omega}^{n-1}(n.2)) = f_{\omega}^n(n.2) = f_{\omega+1}(n.2)\) Next calculation - general formula for \(D(1,m,0)\) \(D(1,0,n+n+1) >> f_{f_{\omega+1}(n.2)}(f_{\omega+1}(n.2)) = f_{\omega}(f_{\omega+1}(n.2))\) \(D(1,0,n+n+2) >> f_{f_{\omega}(f_{\omega+1}(n.2))}(f_{\omega}(f_{\omega+1}(n.2))) = f_{\omega}(f_{\omega}(f_{\omega+1}(n.2))) = f_{\omega}^2(f_{\omega+1}(n.2))\) and \(D(1,0,n.2+m) >> f_{\omega}^m(f_{\omega+1}(n.2))\) Using Rule: NL \(D(l,m,n) = D(l,0,n-1+(m+2).(m+1)/2)\) or \(D(1,m,n) = D(1,0,n-1+(m+2).(m+1)/2)\) then \(D(1,m,0) = D(1,0,0-1+(m+2).(m+1)/2) = D(1,0,(m^2+m.3+2-2)/2)\) \(>> D(1,0,m+m+m)\) when m > 1 and \(>> D(1,0,n.2+m) >> f_{\omega}^m(f_{\omega+1}(n.2))\) when m > n Next calculation - general formula for \(D(1,D(1,0,n),0)\) By definition when \(m = D(1,0,n) > n\) then \(D(1,D(1,0,n),0) >> f_{\omega}^{D(1,0,n)}(f_{\omega+1}(n.2)) >> f_{\omega}^{f_{\omega+1}(n.2)}(f_{\omega+1}(n.2)) = f_{\omega+1}(f_{\omega+1}(n.2))\) \(= f_{\omega+1}^2(n.2)\) Next calculation - general formula for \(D(2,0,n)\) \(D(2,0,0) = D(1,D(1,2,2),D(1,2,2)) = D(1,D(1,0,7),D(1,0,7))\) \(>> D(1,D(1,0,7),0) >> f_{\omega+1}^2(7.2) >> f_{\omega+1}^2(14)\) \(D(2,0,1) = D(1,D(2,0,0),D(2,0,0)) = D(1,D(1,D(1,2,2),D(1,2,2)),D(2,0,0))\) \(>> D(1,D(1,D(1,2,2),D(1,2,2)),0) >> D(1,D(1,D(1,2,2),0),0)\) \(>> D(1,D(1,D(1,0,7),0),0) >> f_{\omega+1}^2(D(1,D(1,0,7),0)) >> f_{\omega+1}^2(f_{\omega+1}^2(14))\) \(>> f_{\omega+1}^2(a)\) where \(a < f_{\omega+1}^2(14)\) then \(D(2,0,n) >> f_{\omega+1}^2(n+\delta)\) where \(\delta >> n\) and \(D(2,0,n) >> f_{\omega+1}^2(n.2)\) Next calculation - getting to \(\omega+2\) \(D(2,0,n+1) = D(1,D(2,0,n),D(2,0,n)) >> D(1,D(2,0,n),D(1,D(2,0,n-1),D(2,0,n-1))\) \(>> D(1,D(2,0,n),D(2,0,n)) >> D(1,D(2,0,n),D(1,D(2,0,n-1),D(2,0,n-1))\) \(>> f_{\omega}^{D(2,0,n)}(f_{\omega+1}(n.2))\) \(>> f_{\omega}^{f_{\omega+1}^2(n.2)}(f_{\omega+1}(n.2)) = f_{\omega}^{f_{\omega+1}^2(n+n)}(f_{\omega+1}(n.2))\) \(>> f_{\omega}^{f_{\omega+1}^2(n)+{f_{\omega+1}^2(n)}(f_{\omega+1}(n.2))\) \(>> f_{\omega}^{f_{\omega+1}^2(n)}(f_{\omega}^{f_{\omega+1}^2(n)}(f_{\omega+1}(n.2)))\) \(= f_{\omega}^{f_{\omega+1}^2(n+n)}(f_{\omega+1}(n.2))\) \(= f_{\omega+1}(f_{\omega+1}©) = f_{\omega+1}^2©\) The rest of this blog is a Work In Progress \(D(2,0,2) = D(1,D(2,0,1),D(2,0,1)) >> f_{\omega}^{m^2/2+m.2}(f_{\omega+1}(3))\) where \(m >> f_{\omega+1}^3(3)\) \(>> f_{\omega}^{m.2}(a)\) where \(m >> f_{\omega+1}^2(a)\) and \(a >> f_{\omega+1}(3))\) \(>> f_{\omega}^{f_{\omega+1}^2(a).2}(a) >> f_{\omega+1}^3(a) = f_{\omega+1}^4(3) = f_{\omega+1}(f_{\omega+2}(3))\) and \(D(2,0,n) >> f_{\omega+1}^{n-1}(f_{\omega+2}(3))\) D(l,0,n) Calculations Let \(D(l-1,0,n) = f_{\phi}^{n-1}(f_{\phi+1}(3))\) where \(\phi\) is any ordinal up to \(\epsilon_0\) then \(D(l,0,0) = D(l-1,D(l-1,l,l),D(l-1,1,1)) >> D(l-1,D(l-1,l,l),0)\) Using Rule: NL from above then \(= D(l,0,(D(l-1,l,l)+2).(D(l-1,l,l)+1)/2-1) >> D(l,0,D(l-1,l,l)+1)\) \(>> D(l,0,D(l-1,0,1)+1) = f_{\phi}^{D(l-1,0,1)}(f_{\phi+1}(3))\) \(= f_{\phi}^{f_{\phi+1}(3)}(f_{\phi+1}(3)) = f_{\phi+1}(f_{\phi+1}(3))\) \(= f_{\phi+1}^2(3)\) and \(D(l,0,1) = D(l-1,D(l,0,0),D(l,0,0)) >> D(l-1,D(l,0,0),0)\) \(>> D(l,0,D(l,0,0)+D(l-1,0,1)+1) = f_{\phi}^{f_{\phi+1}^2(3)+f_{\phi+1}(3)}(f_{\phi+1}(3))\) \(= f_{\phi}^{f_{\phi+1}^2(3)}(f_{\phi+1}^2(3)) = f_{\phi+1}^3(3) = f_{\phi+2}(3)\) and \(D(l,0,2) >> D(l-1,D(l,0,1),D(l,0,1)) >> D(l-1,D(l,0,1),0)\) \(>> D(l,0,D(1,0,1)+D(l,0,0)+D(l-1,0,1)+1) = f_{\phi}^{f_{\phi+2}(3)+f_{\phi+1}^2(3)+f_{\phi+1}(3)}(f_{\phi+1}(3))\) \(= f_{\phi}^{f_{\phi+2}(3)+f_{\phi+1}^2(3)}(f_{\phi+1}^2(3)) = f_{\phi}^{f_{\phi+2}(3)}(f_{\phi+2}(3))\) \(= f_{\phi+1}(f_{\phi+2}(3))\) and when \(D(l,0,n-1) = f_{\phi+1}^{n-2}(f_{\phi+2}(3))\) then \(D(l,0,n) >> D(l-1,D(l,0,n-1),D(l,0,n-1)) >> D(l-1,D(l,0,n-1),0)\) \(>> D(l,0,D(l,0,n-1)+D(l,0,n-2)+D(l,0,n-3)+ ... +D(l,0,1)+D(l-1,0,1)+1)\) \(= f_{\phi}^{f_{\phi+1}^{n-2}(f_{\phi+2}(3))+f_{\phi+1}^{n-3}(f_{\phi+2}(3))+ ... +f_{\phi+1}(f_{\phi+2}(3))+f_{\phi+2}(3)+f_{\phi+1}^2(3)+f_{\phi+1}(3)}(f_{\phi+1}(3))\) \(= f_{\phi}^{f_{\phi+1}^{n-2}(f_{\phi+2}(3))+f_{\phi+1}^{n-3}(f_{\phi+2}(3))+ ... +f_{\phi+1}(f_{\phi+2}(3))+f_{\phi+2}(3)+f_{\phi+1}^2(3)}(f_{\phi+1}^2(3))\) \(= f_{\phi}^{f_{\phi+1}^{n-2}(f_{\phi+2}(3))+f_{\phi+1}^{n-3}(f_{\phi+2}(3))+ ... +f_{\phi+1}(f_{\phi+2}(3))+f_{\phi+2}(3)}(f_{\phi+2}(3))\) \(= f_{\phi}^{f_{\phi+1}^{n-2}(f_{\phi+2}(3))+f_{\phi+1}^{n-3}(f_{\phi+2}(3))+ ... +f_{\phi+1}(f_{\phi+2}(3))}(f_{\phi+1}(f_{\phi+2}(3)))\) \(= f_{\phi}^{f_{\phi+1}^{n-2}(f_{\phi+2}(3))}(f_{\phi+1}^{n-2}(f_{\phi+2}(3)))\) \(= f_{\phi+1}^{n-1}(f_{\phi+2}(3))\) and Rule: LN \(D(l,0,n) >> f_{\phi+1}((D(l,0,n-1)))\) where \(D(l,0,n-1) = f_{\phi+1}^{n-2}(f_{\phi+2}(3))\) and Rule: LG \(D(l,0,n) >> f_{\mu}^{n-1}(f_{\mu+1}(3))\) where \(\mu=\phi+1\) and \(D(l-1,0,n) = f_{\phi}^{n-1}(f_{\phi+1}(3))\) and Rule: L1 \(D(l,0,1) >> f_{\phi+1}(3)\) where \(D(l-1,0,1) = f_{\phi}(3)\) D(l,0,n) Calculations for \(f_{\phi}^{n-1}(f_{\phi+1}(p))\) The purpose of this section is to generalize the rule LN above further and to consider values of p other than 3. Let \(D(l-1,0,n) >> f_{\phi}^{n-q}(f_{\phi+1}(p))\) where \(\phi\) is any ordinal up to \(\epsilon_0\) and q is a small number (say 100) then \(D(l,0,0) = D(l-1,D(l-1,l,l),D(l-1,1,1)) >> D(l-1,D(l-1,l,l),0)\) \(= D(l,0,(D(l-1,l,l)+2).(D(l-1,l,l)+1)/2-1) >> D(l,0,D(l-1,l,l)+K)\) where K is a big number >> q (say 2,000,000) \(>> D(l,0,D(l-1,0,1)+K) = f_{\phi}^{D(l-1,0,1)+K-q}(f_{\phi+1}(p))\) \(>> f_{\phi}^{f_{\phi+1}(p)}(f_{\phi+1}(p)) = f_{\phi+1}(f_{\phi+1}(p))\) \(= f_{\phi+1}^2(p)\) and \(D(l,0,1) = D(l-1,D(l,0,0),D(l,0,0)) >> D(l-1,D(l,0,0),0)\) \(>> D(l,0,D(l,0,0)+D(l-1,0,1)+K) = f_{\phi}^{f_{\phi+1}^2(p)+f_{\phi+1}(p)}(f_{\phi+1}(p))\) \(= f_{\phi}^{f_{\phi+1}^2(p)}(f_{\phi+1}^2(p)) = f_{\phi+1}^3(p)\) and \(D(l,0,2) >> D(l-1,D(l,0,1),D(l,0,1)) >> D(l-1,D(l,0,1),0)\) \(>> D(l,0,D(1,0,1)+D(l,0,0)+D(l-1,0,1)+K) >> f_{\phi+1}^4(p)\) and \(D(l,0,p-2) >> f_{\phi+1}^p(p) = f_{\phi+2}(p)\) \(D(l,0,p-1) = f_{\phi+1}(f_{\phi+2}(p))\) \(D(l,0,p) = f_{\phi+1}^2(f_{\phi+2}(p))\) \(D(l,0,p+1) = f_{\phi+1}^3(f_{\phi+2}(p))\) \(D(l,0,n-1) = f_{\phi+1}^{n-p+1}(f_{\phi+2}(p))\) then ... work in progress \(D(l,0,n) >> D(l-1,D(l,0,n-1),D(l,0,n-1)) >> D(l-1,D(l,0,n-1),0)\) \(>> D(l,0,D(l,0,n-1)+D(l,0,n-2)+D(l,0,n-3)+ ... +D(l,0,1)+D(l-1,0,1)+1)\) \(= f_{\phi}^{f_{\phi+1}^{n-2}(f_{\phi+2}(3))+f_{\phi+1}^{n-3}(f_{\phi+2}(3))+ ... +f_{\phi+1}(f_{\phi+2}(3))+f_{\phi+2}(3)+f_{\phi+1}^2(3)+f_{\phi+1}(3)}(f_{\phi+1}(3))\) \(= f_{\phi}^{f_{\phi+1}^{n-2}(f_{\phi+2}(3))+f_{\phi+1}^{n-3}(f_{\phi+2}(3))+ ... +f_{\phi+1}(f_{\phi+2}(3))+f_{\phi+2}(3)+f_{\phi+1}^2(3)}(f_{\phi+1}^2(3))\) \(= f_{\phi}^{f_{\phi+1}^{n-2}(f_{\phi+2}(3))+f_{\phi+1}^{n-3}(f_{\phi+2}(3))+ ... +f_{\phi+1}(f_{\phi+2}(3))+f_{\phi+2}(3)}(f_{\phi+2}(3))\) \(= f_{\phi}^{f_{\phi+1}^{n-2}(f_{\phi+2}(3))+f_{\phi+1}^{n-3}(f_{\phi+2}(3))+ ... +f_{\phi+1}(f_{\phi+2}(3))}(f_{\phi+1}(f_{\phi+2}(3)))\) \(= f_{\phi}^{f_{\phi+1}^{n-2}(f_{\phi+2}(3))}(f_{\phi+1}^{n-2}(f_{\phi+2}(3)))\) \(= f_{\phi+1}^{n-1}(f_{\phi+2}(3))\) and ... work in progress Rule: LP \(D(l,0,n) >> f_{\phi+1}((D(l,0,n-1)))\) where \(D(l,0,n-1) = f_{\phi+1}^{n-2}(f_{\phi+2}(p))\) Category:Blog posts